public class Solution {

    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A, B, C, A.size());
    }
    public void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n){
        if(n == 1){
            c.add(a.remove(a.size() - 1));
            return ;
        }
        dfs(a, c, b, n - 1);
        c.add(a.remove(a.size() - 1));
        dfs(b, a, c, n - 1);
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) { return list2;}
        if(list2 == null) { return list1;}

        if(list1.val <= list2.val){
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }else{
            list2.next = mergeTwoLists(list2.next, list1);
            return list2;
        }
    }

    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) { return head;}

        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return newHead;
    }

    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) { return head;}

        ListNode tmp = swapPairs(head.next.next);
        ListNode ret = head.next;
        ret.next = head;
        head.next = tmp;
        return ret;
    }

    public double myPow(double x, int n) {
        return n < 0 ? 1.0 / pow(x, -n) : pow(x, n);
    }
    public double pow(double x, int n){
        if(n == 0) { return 1.0;}
        double tmp = pow(x, n / 2);
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }

    public boolean evaluateTree(TreeNode root) {
        if(root.left == null) { return root.val == 0 ? false : true;}

        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);

        return root.val == 2 ? left | right : left & right;
    }

    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    public int dfs(TreeNode root, int prevSum){
        prevSum = prevSum * 10 + root.val;
        if(root.left == null && root.right == null){
            return prevSum;
        }

        int ret = 0;
        if(root.left != null) { ret += dfs(root.left, prevSum);}
        if(root.right != null) { ret += dfs(root.right, prevSum);}
        return ret;
    }

    public TreeNode pruneTree(TreeNode root) {
        if(root == null) { return null;}

        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if(root.left == null && root.right == null && root.val == 0){
            root = null;
        }
        return root;
    }

    long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null) { return true;}

        boolean left = isValidBST(root.left);
        boolean cur = false;
        if(root.val > prev) { cur = true;}

        prev = root.val;
        boolean right = isValidBST(root.right);
        return left && right && cur;
    }

    long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null) { return true;}

        boolean left = isValidBST(root.left);
        if(left == false) { return false;} //剪枝
        boolean cur = false;
        if(root.val > prev) { cur = true;}
        if(cur == false) { return false;}  //剪枝

        prev = root.val;
        boolean right = isValidBST(root.right);
        return left && right && cur;
    }
}
